package 数据结构与算法.排序算法;

import java.time.LocalDateTime;
import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
//        int[] arr={101,34,119,1};
//        insertSort(arr);

        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }

        System.out.println("排序前的时间："+ LocalDateTime.now());

        insertSort(arr);

        System.out.println("排序后的时间："+ LocalDateTime.now());

    }

    //插入排序
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //第一轮
            //定义待插入的数
            int insertVal=arr[i];
            int insertIndex=i-1;//即arr[1]的前面这个数的下标

            //给insertVal找到插入的位置
            //说明
            //1、insertIndex>=0保证在给insertVal找插入位置时不越界
            //2、insertVal<arr[insertIndex]待插入数还没有找到插入位置
            //3、就需要将arr[insertIndex]后移
            while(insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            //当退出while循环时，说明插入位置找到，insertIndex+1
            //判断是否需要赋值
//            if ((insertIndex+1)!=i){
//                arr[insertIndex+1]=insertVal;
//            }
            arr[insertIndex+1]=insertVal;

//            System.out.println("第"+i+"轮插入后：");
//            System.out.println(Arrays.toString(arr));
        }

    }
}
